package ACWing.SearchAndGraphTheory.最短路;
//853. 有边数限制的最短路

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/12/30 21:26
 */
public class BellmanFord {
    static int[]dist=new int[510];
    static int[]backup=new int[510];
    static int n,m,k;
    static class Edge{
        int a;
        int b;
        int w;

        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        k=sc.nextInt();
        Edge[]edges=new Edge[510];
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int w=sc.nextInt();
            edges[i]=new Edge(a,b,w);
        }
        bellman_ford(edges);
        if(dist[n]>0x3f3f3f3f/2){//除二的意义在于负权边可能会导致走不到的点被更新成小于0x3f3f3f3f的数所以小于0x3f3f3f3f/2可以更好判断是否走的到
            System.out.println("impossible");
            return;
        }
        System.out.println(dist[n]);

    }
    public static void bellman_ford(Edge[] edges){
        Arrays.fill(dist,0x3f3f3f3f);
        dist[1]=0;
        for (int i = 0; i < k; i++) {
            backup= Arrays.copyOf(dist, 510);
            for (int j = 0; j < m; j++) {
                int a=edges[j].a,b=edges[j].b,w=edges[j].w;
                dist[b]=Math.min(dist[b],backup[a]+w);
            }
        }

    }
}
